// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem783.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\783.二叉搜索树节点最小距离.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-04-13 09:54:19
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-04-13 10:11:32
 */
/*
 * @lc app=leetcode.cn id=783 lang=cpp
 *
 * [783] 二叉搜索树节点最小距离
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        if(root == NULL)
            return INT_MAX;
        int left = INT_MAX;
        int right = INT_MAX;
        if(root->left != NULL)
        {
            left = root->val - dfsleft(root->left)->val;
        }
        if(root->right != NULL)
        {
            right = dfsright(root->right)->val - root->val;
        }
        
        return min(min(minDiffInBST(root->left),minDiffInBST(root->right)),min(left,right));
    }

    TreeNode* dfsleft(TreeNode *root)
    {
        if(root == NULL)
        {
            return NULL;
        }
        TreeNode *p = root;
        while (p->right != NULL)
        {
            p = p->right;
        }
        return p;
    }
    TreeNode* dfsright(TreeNode *root)
    {
        if(root == NULL)
        {
            return NULL;
        }
        TreeNode *p = root;
        if(p->left == NULL)
        {
            return p;
        }
        while (p->left != NULL)
        {
            p = p->left;
        }
        return p;
    }
};
// @lc code=end

